package cn.lishiyuan.leetcode;


import java.util.List;


public class LeetCode34<T extends  Comparable<T>> {

    /**
     * 有序集合查找元素本质是在两个区间里面查找元素，一个合集总能分成小于(或等于)目标元素的部分和大于（或等于）目标元素的部分。
     * <br>
     * 查找元素的过程就是在左右两个部分中选择查找并逐渐缩小取钱的过程。
     * <br>
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     *
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     *
     * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 8
     * 输出：[3,4]
     * 示例 2：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 6
     * 输出：[-1,-1]
     * 示例 3：
     *
     * 输入：nums = [], target = 0
     * 输出：[-1,-1]
     *
     */
    public int[] searchRange(List<T> list, T target) {
        int first = this.first(list, target);
        if(first == -1){
            // 没有元素
            return new int[]{-1, -1};
        }else if(first == (list.size() -1) ){
            // 第一个元素就是最后一个元素
            return new int[]{first, first};
        }else {
            int last = this.last(list, target);
            return new int[]{first, last};
        }
    }

    /**
     * 给定一个元素，在有序集合中查找第一个等于给定元素的index
     * <br>
     * 思路是在等于之后不再终止而是继续向前查找，直到高位下标小于低位下标
     * <br>
     * 假设【1，3，4，5，5，5，6】中查找5，那么由于大于等于的时候区间会向前移动，小于的时候会向后移动。那么最终high=2，low=3时会结束查找
     */
    public int first(List<T> list, T target){
        int low = 0;
        int high = list.size()-1;
        // 开始查找
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(list.get(mid).compareTo(target) >= 0){
                // 当前元素大于等于目标值，向前查找
                high = mid - 1;
            }else {
                // 如果小于则向后查找
                low = mid + 1;
            }
        }

        // 如果没有越界且等于目标值，则返回。
        if(low < list.size() && list.get(low).compareTo(target) == 0){
            return low;
        }

        return -1;
    }


    /**
     * 给定一个元素，在有序集合中查找最后一个等于给定元素的index
     * <br>
     * 思路是在等于之后不再终止而是继续向后查找，直到高位下标小于低位下标
     * <br>
     * 假设【1，3，4，5，5，5，6】中查找5，那么由于小于等于的时候区间会向后移动，大于的时候会向前移动。那么最终high=5，low=6时会结束查找
     */
    public int last(List<T> list, T target){
        int low = 0;
        int high = list.size()-1;
        // 开始查找
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(list.get(mid).compareTo(target) < 0){
                // 如果小于等于则向后查找
                low = mid + 1;
            }else if(list.get(mid).compareTo(target) > 0) {
                // 当前元素大于目标值，向前查找
                high = mid - 1;
            }else {
                // 如果是最后一个元素 或者 后一个元素不等于则表示已经查找到最后一个等于当前元素的index
                if(mid == (list.size() - 1) || list.get(mid+1).compareTo(target) != 0){
                    return mid;
                }
                // 否则继续向右查找
                low = mid + 1;
            }
        }

        return -1;
    }

    /**
     * 给定一个元素，在有序集合中查找第一个大于等于给定元素的index
     * <br>
     * 思路是在等于之后不再终止而是继续向前查找，直到高位下标小于低位下标
     * <br>
     * 假设【1，3，4，5，5，5，6】中查找第一个大于等于5的元素，那么由于大于等于的时候区间会向前移动，小于的时候会向后移动。那么最终high=2，low=3时会结束查找
     *
     */
    public int firstGte(List<T> list, T target){
        int low = 0;
        int high = list.size()-1;
        // 开始查找
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(list.get(mid).compareTo(target) >= 0){
                // 当前元素大于等于目标值，向前查找
                high = mid - 1;
            }else {
                // 如果小于则向后查找
                low = mid + 1;
            }
        }

        // 如果没有越界且等于目标值，则返回。
        if(low < list.size() && list.get(low).compareTo(target) >= 0){
            return low;
        }

        return -1;
    }

    /**
     * 给定一个元素，在有序集合中查找最后一个小于等于给定元素的index
     * <br>
     * 思路是在等于之后不再终止而是继续向后查找，直到高位下标小于低位下标
     * <br>
     * 假设【1，3，4，5，5，5，6】中查找5，那么由于小于等于的时候区间会向后移动，大于的时候会向前移动。那么最终high=5，low=6时会结束查找
     */
    public int lastLte(List<T> list, T target){
        int low = 0;
        int high = list.size()-1;
        // 开始查找
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(list.get(mid).compareTo(target) <= 0){
                // 如果小于等于则向后查找
                low = mid + 1;
            }else {
                // 当前元素大于目标值，向前查找
                high = mid - 1;
            }
        }

        // 如果没有越界且等于目标值，则返回。
        if(high >= 0  && list.get(high).compareTo(target) >= 0){
            return high;
        }

        return -1;
    }

}
